package com.mdnote.structure.linked_list;

/**
 * @author Rhythm-2019
 * @date 2020/8/9
 * @description 链表
 */
public class SingleLinkedList<T extends Comparable<T>> {

    private static class Node<T> {
        private T val;
        private Node<T> next;

        public Node(T val) {
            this.val = val;
        }
    }

    // 头部
    private Node<T> head;

    public SingleLinkedList() {
        this.head = new Node<>(null);
        this.head.next = null;
    }

    // 添加元素
    public void add(Node<T> node) {
        Node<T> tmp = head;
        while (tmp.next != null) {
            tmp = tmp.next;
        }
        tmp.next = node;
    }

    // 按顺序添加元素tmp
    public void addByOrder(Node<T> node) {

        Node<T> tmp = head;
        while (tmp.next != null) {
            // 比较大小，注意时用下一个元素去比
            if (tmp.next.val != null && ((Comparable) (tmp.next.val)).compareTo(node.val) > 0) {
                break;
            }

            tmp = tmp.next;
        }
        node.next = tmp.next;
        tmp.next = node;
    }

    // 删除指定元数
    public void remove(Node<T> node) {
        Node<T> temp = this.head;
        while (temp.next != null && temp.next !=  node) {
            // 找到对应的元素的上一个元素
            temp = temp.next;
        }
        // 没找到
        if (temp.next == null) {
            System.out.println("no found the element");
        } else {
            temp.next = temp.next.next;
        }
    }

    public void edit(Node<T> node, T val) {
        Node<T> temp = this.head;
        while (temp.next != null && temp.next !=  node) {
            // 找到对应的元素的上一个元素
            temp = temp.next;
        }
        // 没找到
        if (temp.next == null) {
            System.out.println("no found the element");
        } else {
            temp.next.val = val;
        }
    }

    public void show() {
        Node<T> tmp = head;
        while (tmp != null) {
            System.out.print(tmp.val + "->");
            tmp = tmp.next;
        }
    }

    public void reverse() {
        Node<T> cur = this.head.next;  // 从第一个元素开始
        if (cur == null || cur.next == null || cur.next.next == null) {
            return;
        }
        Node<T> reverse = new Node<>(null);
        while (cur != null) {
            Node<T> next = cur.next; // 保存下一个元素
            cur.next = reverse.next;  // 让cur指向reverse的下一个元素
            reverse.next = cur;  // 让reverse指向cur
            cur = next;
        }
        head.next = reverse.next; // head指向reverse的下一个元素
    }


    public static void main(String[] args) {
        Node<Integer> node2 = new Node<>(33);
        Node<Integer> node3 = new Node<>(22);
        Node<Integer> node1 = new Node<>(11);

        SingleLinkedList<Integer> linkedList = new SingleLinkedList<>();
        linkedList.addByOrder(node1);
        linkedList.addByOrder(node2);
        linkedList.addByOrder(node3);

//        linkedList.edit(node1, 55);

        linkedList.reverse();
        linkedList.show();
    }
}
